class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        dp1 = [[False for _ in range(n+1)] for _ in range(n+1)]  # 判断位置上是否为回文串
        dp1[0][0] = True
        for i in range(n, 0, -1):
            for j in range(i,n+1) :
                if s[i-1] == s[j-1] and i < n and j > 0:
                    dp1[i][j] |= dp1[i+1][j-1]
                if i == j:
                    dp1[i][j] = True
                if j == i + 1 and s[j-1] == s[i-1]:
                    dp1[i][j] = True
        dp = [float('inf') for _ in range(n+1)]
        dp[0] = 0
        dp[1] = 0
        for r in range(1, n+1):
            for l in range(1,r+1):
                if dp1[l][r]:
                    dp[r] = min(dp[l-1]+1,dp[r])
                    if l == 1:
                        dp[r] = 0
        return dp[n]

if __name__ == '__main__':
    s = Solution()
    r = s.minCut("aab")
    print(r)

